#define _CRT_SECURE_NO_WARNINGS 1
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

struct val_list
{
    int val;
    ListNode* cur;

    bool operator>(const val_list& vl) const
    {
        return val > vl.val;
    }
    val_list(int v, ListNode* c)
        :val(v), cur(c)
    {}
};
class Solution {
public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* newhead = new ListNode(0);
        int n = lists.size();
        priority_queue<val_list, vector<val_list>, greater<val_list>> pq;
        for (auto list : lists) if (list) pq.push({ list->val, list });
        ListNode* pcur = newhead;
        while (pq.size())
        {
            pcur->next = pq.top().cur;
            pq.pop();
            pcur = pcur->next;
            if (pcur->next) pq.push({ pcur->next->val, pcur->next });
        }

        return newhead->next;
    }
};